Search for: All records

This paper answers a long-standing open question in tile-assembly theory, namely that it is possible to strictly assemble discrete self-similar fractals (DSSFs) in the abstract Tile-Assembly Model (aTAM). We prove this in 2 separate ways, each taking advantage of a novel set of tools. One of our constructions shows that specializing the notion of a quine, a program which prints its own output, to the language of tile-assembly naturally induces a fractal structure. The other construction introduces self-describing circuits as a means to abstractly represent the information flow through a tile-assembly construction and shows that such circuits may be constructed for a relative of the Sierpinski carpet, and indeed many other DSSFs, through a process of fixed-point iteration. This later result, or more specifically the machinery used in its construction, further enable us to provide a polynomial time procedure for deciding whether any given subset of ℤ2 will generate an aTAM producible DSSF. To this end, we also introduce the Tree Pump Theorem, a result analogous to the important Window Movie Lemma, but with requirements on the set of productions rather than on the self-assembling system itself. 

The abstract Tile Assembly Model (aTAM) provides an excellent foundation for the mathematical study of DNA-tile-based self-assembling systems, especially those wherein logic is embedded within the designs of the tiles so that they follow prescribed algorithms. While such algorithmic self-assembling systems are theoretically powerful, being computationally universal and capable of building complex shapes using information-theoretically optimal numbers of tiles, physical DNA-based implementations of these systems still encounter formidable error rates and undesired nucleation that hinder this theoretical potential. Slat-based self-assembly is a recent development wherein DNA forms long slats that combine together in 2 layers, rather than square tiles in a plane. In this approach, the length of the slats is key; while tiles typically only bind to 2 neighboring tiles at a time, slats may bind to dozens of other slats. This increased coordination between slats means that several mismatched slats must coincidentally meet in just the right way for errors to persist, unlike tiles where only a few are required. Consequently, while still a novel technology, large slat-based DNA constructions have been successfully implemented in the lab with resilience to many tile-based construction problems. These improved error characteristics come at a cost however, as slat-based systems are often more difficult to design and simulate than tile-based ones. Moreover, it has not been clear whether slats, with their larger sizes and different geometries, have the same theoretical capabilities as tiles. In this paper, we show that slats are capable of doing anything that tiles can, at least at scale. We demonstrate that any aTAM system may be converted to and simulated by an effectively equivalent system of slats. Furthermore, we show that these simulating slat systems can be made more efficiently, using shorter slats and a smaller scale factor, if the simulated tile system avoids certain uncommon growth patterns. Specifically, we consider 5 classes of aTAM systems with increasing complexity, from zig-zag systems which grow in a rigid pattern to the full class of all aTAM systems, and show how they may be converted to equivalent slat systems. We show that the simplest class may be simulated by slats at only a 2c × 2c scale, where c is the freely chosen coordination number of the slats, and further show that the full class of aTAM systems can be simulated at only a 5c × 5c scale. These results prove that slats have the full theoretical power of aTAM tiles while also providing constructions that are compact enough for potential DNA-based implementations of slat systems that are both capable of powerful algorithmic self-assembly and possessing of the strong error resilience of slats. 

We present an abstract model of self-assembly of systems composed of "crisscross slats", which have been experimentally implemented as a single-stranded piece of DNA [Minev et al., 2021] or as a complete DNA origami structure [Wintersinger et al., 2022]. We then introduce a more physically realistic *kinetic* model and show how important constants in the model were derived and tuned, and compare simulation-based results to experimental results [Minev et al., 2021; Wintersinger et al., 2022]. Using these models, we show how we can apply optimizations to designs of slat systems in order to lower the numbers of unique slat types required to build target structures. In general, we apply two types of techniques to achieve greatly reduced numbers of slat types. Similar to the experimental work implementing DNA origami-based slats, in our designs the slats oriented in horizontal and vertical directions are each restricted to their own plane and sets of them overlap each other in square regions which we refer to as macrotiles. Our first technique extends their previous work of reusing slat types within macrotiles and requires analyses of binding domain patterns to determine the potential for errors consisting of incorrect slat types attaching at undesired translations and reflections. The second technique leverages the power of algorithmic self-assembly to efficiently reuse entire macrotiles which self-assemble in patterns following designed algorithms that dictate the dimensions and patterns of growth. Using these designs, we demonstrate that in kinetic simulations the systems with reduced numbers of slat types self-assemble more quickly than those with greater numbers. This provides evidence that such optimizations will also result in greater assembly speeds in experimental systems. Furthermore, the reduced numbers of slat types required have the potential to vastly reduce the cost and number of lab steps for crisscross assembly experiments.